\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}
\sloppy

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Проверочная работа 1. Исправления}

\paragraph{2.} Сколько битовых слов длины $n$ содержат четное число нулей?
\begin{Solution}
Правильный ответ $2^{n-1}$, докажем это. Рассмотрим случай нечетных $n$. Если битовое слово содержит четное число нулей, то его инверсия содержит нечетное число нулей, и для каждого битового вектора есть инверсный, т. е. количество векторов с четным числом нулей составляет ровно половину от всех битовых векторов, т. е. $2^{n-1}$. Теперь рассмотрим случай четного $n$, отбросим один бит, и будем рассматривать битовые вектора длины $n-1$, где $n-1$ - нечетное число, а значит число таких векторов с четным числом нулей $2^{n-2}$ и такое же количество векторов с нечетным числом нулей. Теперь вернем первый бит, если бит $0$ и число нулей в $n-1$ слове четное, то в полученном $n$ слове оно будет нечетно, а если число нулей в $n-1$ слове было нечетно, то в полученном $n$ слове оно будет четно, таких слов очевидно $2^{n-2}$, если первый бит $1$ и число нулей четно, то и в $n$ слове их число останется четным, число таких слов $2^{n-2}$, а если число нулей в $n-1$ слове нечетно, то и в $n$ слове оно останется нечетным, теперь просуммируем число $n$ слов с четным числом нулей:
\[
	2^{n-2} + 2^{n-2} = 2 \cdot 2^{n-2} = 2^{n-1}
\]
\end{Solution}

\paragraph{4.} Сколько чисел меньше миллиона можно записать с помощью цифр $8$ и $9$?
\begin{Solution}
Меньше миллиона будут все $6$, $5$, $4$, $3$, $2$, и $1$ -значные числа, т. е. результат:
\[
	\sum_{i=1}^6 2^i
\]
\end{Solution}

\paragraph{6. 1} Поезд с $20$ пассажирами делает $7$ остановок. Сколько способов у пассажиров выйти из поезда на этих остановках (если учитиывается, что все пассажиры разные)
\begin{Solution}
Каждый из 20 пассажиров может выбрать одну из семи остановок, получается:
\[
	7^{20}
\]
\end{Solution}

\paragraph{8. 1} Сколькими способами можно рассадить 5 мужчин и 5 женщин в ряд, так чтобы никакие двое мужчин или две женщины не сидели рядом?
\begin{Solution}
Женщины и мужчины чередуются в ряду, женщин и мужчин можно переставлять незаисимо дург от друга, рассмотрим случай когда в ряду первая женщина, количетсво таких расстановок $5! \cdot 5!$, если в ряду первый мужчина получаем тоже количество, следовательно результат:
\[
	2 \cdot 5! \cdot 5!
\]
\end{Solution}

\paragraph{9. 4} Сколькими способами можно выбрать 3 краски из 5 и сделать из них флаг, если цвета в флаге могут повторяться, но не рядом?
\begin{Solution}
Пусть флаг состоит из трех горизонтальных полосок. Рассмотрим случай когда все три цвета различны, количество способов составить из них флаг (порядок цветов важен): $5 \cdot 4 \cdot 3$. Выбор цветов с повторениями, так чтобы в флаге они не стояли рядом экваивалентен выбору двух различных цветов из 5 с учетом порядка: $5 \cdot 4$, просуммировав получаем:
\[
	5 \cdot 4 \cdot 3 + 5 \cdot 4 = 5 \cdot 4 \cdot \left( 3 + 1 \right) = 5 \cdot 4^2
\]
\end{Solution}

\paragraph{11. 1} Сколько целочисленных неотрицательных решений имеет уравнение $a_1 + a_2 + a_3 + a_4 + a_5 = 25$?
\begin{Solution}
Имеется 25 единиц, требуется распределить их по 5 позициям:
\[
	\left( \binom{5}{25} \right)
\]
\end{Solution}

\end{document}
